Random access memory (RAM) devices generally comprise a plurality of data storage locations, each data storage location having a corresponding predetermined address. FIG. 1 illustrates a conventional RAM device 10. As illustrated in FIG. 1, the RAM device 10 has address fields that are each eight bits in length. Accordingly, the RAM device 10 has 256 unique addresses. Because there is a one-to-one correspondence of addresses to data storage locations, there are 256 data storage locations (fields) in the RAM device 10. The RAM device 10, however, could have other address field lengths and, thus, a different number of unique addresses and corresponding storage locations.
The RAM device 10 includes an address port 12, a data port 14 and a read/write control input 16. To store data in a data storage location of the RAM device 10, the address of the location in which the data is to be stored is applied to the address port 12 and the data to be stored is applied to the data port 14. Then, the read/write control input 16 is conditioned to write the data into the location specified by the address. To read data from the RAM device 10, the read/write control input 16 is conditioned to read data and the address of the location from which the data is to be read from is applied to the address port 12. The data stored in the location specified by the address appears at the data port 14.
Content addressable memory (CAM) devices generally comprise a plurality of data storage locations, each data storage location having a predetermined corresponding address. CAM devices are characterized in that each data storage location includes a comparand field and an associated data field. Comparands are stored in the comparand fields, while data associated with each comparand is stored in the associated data field. Data from the associated data fields is read by comparing each comparand to an applied value. When a match occurs, the contents of the associated data field corresponding to the matching comparand are read.
FIG. 2 illustrates a conventional CAM device 20. As illustrated in FIG. 2, the CAM device 20 has address fields that are each eight bits in length. Accordingly, the CAM device 20 has 256 unique addresses. Because there is a one-to-one correspondence of addresses to data storage locations, there are 256 data storage locations in the CAM device 20, each data storage location including a comparand field and an associated data field. The CAM device 20, however, could have other address field lengths and, thus, a different number of unique addresses and corresponding storage locations.
The CAM device 20 includes an address port 22, a comparand port 24, an associated data port 26, a read/write control input 28 and a match output 29. To store a comparand and associated data in the CAM device 20, a desired address is applied to the address port 22, the desired comparand is applied to the comparand port 24 and the desired associated data is applied to the associated data port 26. Then, the control input 28 is conditioned to write the comparand and the associated data into the location specified by the address.
To read associated data from the CAM device 20, the control input is conditioned to read data and a specified value is applied to the comparand port 24. If a stored comparand matches the specified value applied to the comparand port 24, this condition will be indicated by the match output 29. Data stored in the associated data field which corresponds to the matching comparand appears at the associated data port 26. Otherwise, if no comparand matches the value applied to the comparand port 24, the match output 29 will indicate this condition.
Therefore, to read associated data from the CAM device 20, the value applied to the comparand port 24 is compared to the previously stored contents of all the comparand fields. When a match is found, the associated data appears at the data port 26. Accordingly, the memory device 20 is referred to as "content addressable."
Because of this "content addressable" feature, CAM devices are typically more expensive to manufacture and to purchase than RAM devices, however, CAM devices are particularly well suited for certain applications. For example, a CAM device can be utilized to construct a look-up table for appropriately directing data packets through a multi-port bridge in a local area network (LAN). FIG. 3 illustrates a conventional local area network including a multi-port bridge 30. The multi-port bridge 30 has eight ports #A-F, though the number of ports can vary. Each port #A-F is connected to a segment 31-38 of the LAN. Each segment 31-38 typically includes one or more nodes 39-54, such as a workstation, a personal computer, a data terminal, a file server, a printer, a facsimile, a scanner or other conventional digital device. Each of the nodes 39-54 has an associated node address which uniquely identifies the node. The nodes 39-54 are configured to send data, one to another, in the form of discrete data packets.
When the LAN operates according to Ethernet standards, such as the Institute of Electrical and Electronics Engineers (IEEE) 802.3 standard, data is communicated in the form of discrete packets. FIG. 4 illustrates a conventional IEEE 802.3 data packet 60. The data packet 60 includes an eight byte long pre-amble 61 which is generally utilized for synchronizing a receiver to the data packet 60. The pre-amble 61 includes seven bytes of preamble and one byte of start-of-frame. Following the pre-amble 61, the data packet 60 includes a six-byte-long destination address 62, which is the node address of a node which is an intended recipient for the data packet 60. Next, the data packet 60 includes a six-byte-long source address 63, which is the node address of a node which originated the data packet 60. Following the source address 63 is a two-byte length field 64. Following the length field 64 is a data field 65. The data field 65 can be up to 1500 bytes long. Finally, the data packet 60 includes a two-byte frame check field 66 which allows a recipient of the data packet 60 to determine whether an error has occurred during transmission of the data packet 60.
When a node (source node) sends data to another node (destination node) located on its same segment of the LAN (intra-segment communication), the data is communicated directly between the nodes without intervention by the multi-port bridge 30 and is known as an intra-segment packet. Therefore, when the multi-port bridge 30 receives an intra-segment packet, the multi-port bridge 30 does not bridge the packet (the packet is filtered). When a node (source node) sends a data packet to another node (destination node) located on a different segment (inter-segment communication), the multi-port bridge 30 appropriately forwards the data packet to the destination node.
The multi-port bridge 30 (FIG. 3) receives each data packet 60 (FIG. 4) and must determine whether the data packet 60 is for intra-segment communication or inter-segment communication, and if the data packet 60 is for inter-segment communication, the multi-port bridge 30 must determine which port (destination port) the data packet 60 is to be directed based upon the destination address 62 contained in the data packet 60. This can be accomplished with a look-up table constructed in a CAM device 20 (FIG. 2). Conventionally, the look-up table is constructed by executing a learning phase for each received data packet 60 to store data in the table and by executing a look-up phase for each received data packet 60 to look-up data stored during the learning phase for a prior packet.
An example is provided to enhance understanding of the learning phase. To understand the example, one should refer to FIGS. 2, 3 and 4. The learning phase is executed by storing in the address field of the CAM device 20 the address of the node (source node) which sends a data packet 60 and storing in the corresponding data field the number of the port (source port) which received the data packet 60. For example, referring to FIG. 3, if the node 39 sends a data packet 60 to the node 50, the data packet 60 will include the address of the node 39 as its source address. The multi-port bridge 30 will receive the data packet 60 from port #1. Therefore, for the learning phase, the address of the node 39 will be stored in the address field of the CAM device 20 and a number identifying the port #1 will be stored in the corresponding data field. This process is repeated for each data packet 60 received by the multi-port bridge 30.
Once the look-up table is constructed, to appropriately direct a next data packet 60, the destination address contained in the data packet 60 is applied to the address port 22 of the CAM, while the data port 24 of the CAM will indicate to which port (destination port) the packet is to be directed. In the example, the node 50 is the intended recipient. Thus, the data packet will include the address of the node 50 as its destination address The node 50 is connected to the port #6. Therefore, when the address of the node 50 is applied to the address port 22 of the CAM device 20, the data port 24 of the CAM device 20 will indicate that the data packet 60 should be routed to the port #6. Data packets 60 received before the table is completed are broadcast to all the ports #1-8 to ensure that the appropriate destination node receives the packet.
To save costs, the CAM device 20 can be emulated by a RAM device through a technique known as hashing. Hashing is a mathematical technique of mapping a larger set of numbers into a smaller set. For example, in an Ethernet LAN, each node is specified by an address that is six bytes (48 bits long. Therefore, there are 2.sup.48 (approximately 2.8.times.10.sup.14) possible addresses. Using a RAM device to store a port number associated with each of these possible addresses would require a RAM device having 2.sup.48 memory locations. Construction of such a large RAM device would tend to be impractical and would almost certainly exceed the cost and space requirements of an appropriately sized CAM device. Because Ethernet LANs generally have far fewer than 2.sup.48 nodes, hashing can be utilized to construct a look-up table having far fewer than 2.sup.48 entries.
According to the IEEE 802.3 standard, a look-up table is required to accurately reflect nodes which have been newly added or removed from the LAN. For this purpose, each node of the LAN periodically transmits a "keep alive" packet, preferably once every 2.5 minutes. Entries in a look-up table which have not been updated within a predetermined time period, preferably five minutes, are removed from the look-up table.
A known technique for updating such a look-up table in an Ethernet LAN includes storing a time stamp in the look-up table along with every entry and updating the time stamp whenever the corresponding node originates a data packet. In addition, the technique requires keeping track of the age of every entry in the look-up table, and when an entry becomes more than five minutes old, removing the entry. This technique has a disadvantage in that a large amount of processing overhead is required to provide a time stamp for each entry in the table, to update the time stamps, to keep track of the time elapsed since a last update for each entry, and to remove entries after five minutes have elapsed since the last update for the entry. Also, additional storage space is required for storing the time stamps.
Therefore, what is needed is an improved technique for periodically updating the entries in a CAM device. What is further needed is an improved technique for periodically updating the entries in a CAM device emulated by a RAM device. What is still further needed in an improved technique for periodically updating the entries in a look-up table utilized for appropriately directing data through a multi-port bridge in an Ethernet LAN.